(* tree.ml: arbres binaires simples *)
 
type 'a tree =
    Empty
  | Node of 'a tree * 'a * 'a tree
 
(* Constructeurs *)
let empty = Empty
let node ls k rs = Node(ls,k,rs)
 
(* Accesseurs *)
let is_empty t = t = Empty
let is_leaf = function
  | Node(Empty,_,Empty) -> true
  | _ -> false
 
(* Parcours *)
 
(* iter en profondeur (depth first) *)
let rec dfiter prefix infix suffix  = function
  | Empty -> ()
  | Node(ls,k,rs) ->
      begin
	prefix k;
	dfiter prefix infix suffix ls;
	infix k;
	dfiter prefix infix suffix rs;
	suffix k
      end
 
(* Affichage "propre" *)
  let print f t =
    let rec aux f = function
	Empty -> Format.printf "Empty@,"
      | Node (ls,k,rs) ->
	  begin
	    Format.printf "@[<b 2>Node(@,";
	    aux f ls;
	    Format.printf ",@;%s,@;" (f k);
	    aux f rs;
	    Format.printf ")@]@,";
	  end
    in
      aux f t;
      Format.printf "@,"

